On Tree Representations of Relations and Graphs: Symbolic Ultrametrics and Cograph Edge Decompositions

摘要

Tree representations of (sets of) symmetric binary relations, or equivalentlyedge-colored undirected graphs, are of central interest, e.g.\ inphylogenomics. In this context symbolic ultrametrics play a crucial role.Symbolic ultrametrics define an edge-colored complete graph that allows torepresent the topology of this graph as a vertex-colored tree. Here, we areinterested in the structure and the complexity of certain combinatorialproblems resulting from considerations based on symbolic ultrametrics, and onalgorithms to solve them. This includes, the characterization of symbolic ultrametrics thatadditionally distinguishes between edges and non-edges of \emph{arbitrary}edge-colored graphs $G$ and thus, yielding a tree representation of $G$, bymeans of so-called cographs. Moreover, we address the problem of finding"closest" symbolic ultrametrics and show the NP-completeness of the threeproblems: symbolic ultrametric editing, completion and deletion. Finally, asnot all graphs are cographs, and hence, don't have a tree representation, weask, furthermore, what is the minimum number of cotrees needed to represent thetopology of an arbitrary non-cograph $G$. This is equivalent to find an optimalcograph edge $k$-decomposition $\{E_1,\dots,E_k\}$ of $E$ so that each subgraph$(V,E_i)$ of $G$ is a cograph. We investigate this problem in full detail,resulting in several new open problems, and NP-hardness results. For all optimization problems proven to be NP-hard we will provide integerlinear program (ILP) formulations to efficiently solve them.